package comprehensive;

import java.util.ArrayList;
import java.util.List;

public class Exercises7 {
    // 39、组合总数
    List<List<Integer>> ret;
    List<Integer> path;
    int t;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        t = target;

        dfs(candidates,0,0);

        return ret;
    }

    public void dfs(int[] nums,int pos,int sum) {
        // pos也是下标
        // pos 是从哪个位置开始，不能遍历 2 3 5 遍历到3数据了，不能再找2了，因为在2那个时候，就存在2 3了，再从3选2的话，就是3 2重复了

        if (sum == t) {
            ret.add(new ArrayList<>(path));
            return;
        }
        // 在下面这些条件中，如果满足一个就不符合题意，如果pos和数组长度相等，就说明遍历数组到最后了，可以返回了
        if (sum > t || pos == nums.length) {
            return;
        }
        // 方法二：进行优化
        // 我们可以从每一个数据选择的次数进行解决这个问题
        for(int k = 0;k * nums[pos] + sum <= t;k++) {
            if(k != 0) {
                path.add(nums[pos]);
            }
            dfs(nums,pos + 1,k * nums[pos] + sum);
        }

        // 把每一个数据的次数都进行计算完成之后，直至sum超过目标值，再来整体进行回溯->恢复现场
        // k需要从1开始，因为我们放入数据的时候是从1开始的，k为0位置没有进行放入元素
        for(int k = 1;k * nums[pos] + sum <= t;k++) {
            path.remove(path.size() - 1);
        }

//        // 这个是在每层进行选择哪个数据，之后i是不能往前选的，比如，这一层是下标2开始的，下一层就不能从下标1或者0开始
//        for(int i = pos;i < nums.length;i++) {
//            path.add(nums[i]);
//            // 因为可以选择重复元素，所以要从原来的位置开始遍历下一层的位置
//            dfs(nums,i,sum + nums[i]);
//            // 回溯->恢复现场
//            path.remove(path.size() - 1);
//        }
    }
}
